#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    string longestPalindrome(string s)
    {
        if (s.size() == 0)
            return "";
        vector<int> range(2, 0);
        for (int i = 0; i < s.size(); i++)
        {
            i = findLongest(s, i, range);
        }
        return s.substr(range[0], range[1] - range[0] + 1);
    }
    int findLongest(string str, int low, vector<int> &range)
    {
        int high = low;
        while (high < str.size() - 1 && str[high + 1] == str[low])
        {
            high++;
        }
        int ans = high;
        while (low > 0 && high < str.size() - 1 && str[low - 1] == str[high + 1])
        {
            low--;
            high++;
        }
        if (high - low > range[1] - range[0])
        {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }
};